package com.zcmyth;

import java.util.List;

public class BinarySearch {

  /**
   * Search the first element that equals to target.
   * 
   * @return -1 if there is no element equals target.
   */
  public static <T extends Comparable<T>> int binarySearch(List<T> list, T target) {
    int l = 0;
    int r = list.size() - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      int result = list.get(mid).compareTo(target);
      if (result == 0) {
        r = mid;
        if(l == r) {
          break;
        }
      } else if (result < 0) {
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    return r;
  }
}